<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 创建列表类
    function ArrayList () {
        // 属性
        this.array = []

        // 方法
        // 插入
        ArrayList.prototype.insert = function (item) {
            this.array.push(item)
        }

        // toString
        ArrayList.prototype.toString = function () {
            return this.array.join('-')
        }

        // 交换两个位置的数据
        ArrayList.prototype.swap = function (m, n) {
            var temp = this.array[m]
            this.array[m] = this.array[n]
            this.array[n] = temp
        }


        // 实现排序算法
        // 冒泡排序
        ArrayList.prototype.bubblesort = function () {
            // 1.获取数组的长度
            var length = this.array.length

            // 2.循环比较
            for (var j = length - 1; j >= 0; j--) {
                for (var i = 0; i < j; i++) {
                    if (this.array[i] > this.array[i+1]) {
                        this.swap(i, i+1)
                    }
                }
            }
        }

        // 选择排序
        ArrayList.prototype.selectionSort = function () {
            var length = this.array.length

            for (var j = 0; j < length - 1; j++) {
                var min = j
                for (var i = min + 1; i < length; i++) {
                    if (this.array[min] > this.array[i]) {
                        min = i
                    }
                }
                this.swap(min, j)
            }
        }

        // 插入排序
        ArrayList.prototype.insertionSort = function () {
            var length = this.array.length

            for (var i = 1; i < length; i++) {
                var temp = this.array[i]
                var j = i
                while (this.array[j - 1] > temp && j > 0) {
                    this.array[j] = this.array[j - 1]
                    j--
                }
                this.array[j] = temp
            }
        }

        // 希尔排序
        ArrayList.prototype.shellSort = function () {
            var length = this.array.length

            // 初始化增量
            var gap = Math.floor(length / 2)

            // while循环(gap不断减小)
            while (gap >= 1) {
                for (var i = gap; i < length; i++) {
                    var temp = this.array[i]
                    var j = i
                    while (this.array[j - gap] > temp && j > gap -1) {
                        this.array[j] = this.array[j - gap]
                        j -= gap
                    }
                    this.array[j] = temp
                }
                gap = Math.floor(gap / 2)
            }
        }
    }

    // 测试类
    var list = new ArrayList()

    // 插入数据
    list.insert(66)
    list.insert(88)
    list.insert(11)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(565)
    list.insert(23)

    // 验证冒泡排序
    // list.bubblesort()
    // alert(list)

    // 验证选择排序
    // list.selectionSort()
    // alert(list)

    // 验证希尔排序
    list.shellSort()
    alert(list)
</script>
</body>
</html>
